/**
 * 剑指 Offer 35. 复杂链表的复制
 * https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
 */
const { displayListNode, createListNode } = require('../../libs/public');

function Node(val, next, random) {
  this.val = val;
  this.next = next;
  this.random = random;
}

/**
 * @param {Node} head
 * @return {Node}
 */
function copyRandomList(head) {
  if (!head) {
    return null;
  }
  const map = new WeakMap();
  let size = 0;
  let node = head;
  while (node) {
    map.set(node, size);
    size += 1;
    node = node.next;
  }
  const cache = new Array(size);
  cache[0] = new Node(head.val, null, null);
  let i = 1;
  let lastNode = cache[0];
  node = head.next;
  while (node) {
    cache[i] = new Node(node.val, null, null);
    lastNode.next = cache[i];
    lastNode = cache[i];
    i += 1;
    node = node.next;
  }
  node = head;
  i = 0;
  while (node) {
    if (node.random) {
      cache[i].random = cache[map.get(node.random)];
    }
    node = node.next;
    i += 1;
  }
  return cache[0];
}

// /**
//  * @param {Node} head
//  * @return {Node}
//  */
// function copyRandomList(head) {
//   if (!head) {
//     return null;
//   }
//   let node = head;
//   while (node) {
//     const newNode = new Node(node.val, node.next, null);
//     node.next = newNode;
//     node = node.next.next;
//   }
//   node = head;
//   while (node) {
//     const newNode = node.next;
//     if (node.random) {
//       newNode.random = node.random.next;
//     }
//     node = node.next.next;
//   }
//   const result = head.next;
//   node = head;
//   while (node) {
//     const newNode = node.next;
//     node.next = newNode.next;
//     node = node.next;
//     newNode.next = node ? node.next : null;
//   }
//   return result;
// }

console.log(displayListNode(copyRandomList(createListNode([7, 13, 14, 10, 1]))));
